package leetcode.leetcode_hot100;

/**
 * @ClassName T0096
 * @Description 不同的二叉搜索树
 * @Author Fanxc
 * @DATE 2021/6/19 20:29
 * @Version 1.0
 */
public class T0096 {
    //i为根节点，左右子树的个数分别为i-1,n-i
    class Solution {
        public int numTrees(int n) {
            int[] G=new int[n+1];
            G[0]=1;
            G[1]=1;
            for(int i=2;i<=n;i++){
                for(int j=1;j<=i;j++){
                    G[i]+=G[j-1]*G[i-j];
                }
            }
            return G[n];
        }
    }

}
